package com.mid;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by Lxk on 2019/8/11.
 */
public class Solution452 {

    static class Balloon implements Comparable<Balloon> {

        private int xLeft;

        private int xRight;

        public Balloon(int xLeft, int xRight) {
            this.xLeft = xLeft;
            this.xRight = xRight;
        }

        @Override
        public int compareTo(Balloon o) {
            return this.xLeft - o.xLeft;
        }
    }

    public int findMinArrowShots(int[][] points) {
        int res = 0;
        if (points == null || points.length == 0) {
            return res;
        }
        List<Balloon> balloons = new ArrayList<>();
        for (int[] point : points) {
            Balloon balloon = new Balloon(point[0], point[1]);
            balloons.add(balloon);
        }
        Collections.sort(balloons);
        int end = balloons.get(0).xRight;
        res = 1;
        for (int i = 1; i < balloons.size(); i++) {
            Balloon cur = balloons.get(i);
            if (end > cur.xLeft) {
                end = Math.min(end, cur.xRight);
            } else {
                res++;
                end = cur.xRight;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] data = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        Solution452 solution452 = new Solution452();
        System.out.println(solution452.findMinArrowShots(data));
        ;
    }


}
